class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        sort(nums.begin(), nums.end());
        for (const auto& e : nums)
            sum += e;
        if (sum % 2 != 0)
            return false;
        vector<int> dp(sum / 2 + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = sum / 2; j >= nums[i]; j--) {
                if (dp[j - nums[i]])
                    dp[j] = 1;
            }
        }
        return dp[sum / 2];
    }
};